package com.hspedu.newData.dmsxl.动态规划.基础;

import java.util.*;

/**
 * @Author: yh
 * @description: 
 * @CreateTime: 2025-05-16 
 * @Version: 1.0
 */

public class LC2901最长相邻不相等子序列Ⅱ {

    // todo
    // 效率不高
    public List<String> getWordsInLongestSubsequence(String[] words, int[] groups) {

        int len = words.length;
        int[] dp = new int[len];
        int[] index = new int[len];

        Arrays.fill(dp,1);
        Arrays.fill(index,-1);
        int maxIndex = 0;
        for (int i = 1; i < len; i++) {
            for (int j = 0; j < i; j++) {
                if (check(words[i],words[j]) && dp[j] + 1 > dp[i] && groups[i] != groups[j]){
                    dp[i] = dp[j] + 1;
                    index[i] = j;
                }
            }
            if (dp[i]>dp[maxIndex]){
                maxIndex = i;
            }
        }

        List<String> ans = new ArrayList<>();
        for (int i = maxIndex; i >= 0; i = index[i]) {
            ans.add(words[i]);
        }
        Collections.reverse(ans);
        return ans;
    }

    public boolean check(String str,String ptr){
        int count = 0;

        if (str.length() != ptr.length()){
            return false;
        }

        for (int i = 0; i < str.length(); i++) {
            if (str.charAt(i) != ptr.charAt(i)){
                count++;
            }
            if (count > 2){
                return false;
            }
        }
        return count == 1;
    }
}
